package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ListNode;
import com.cuz.daileetcode.utils.ListNodeUtils;

import java.util.Objects;
import java.util.Stack;

public class Day27 {


    /***
     * 单链表是否回文
     * 使用栈实现
     * 首先把每一个节点的值进行压栈
     * 后再次遍历，如果每次节点都和pop的值一样 那么回文
     * 反之不回文
     */
    public static boolean isTheSingleLinkedListPalindrome1(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode temp = head;
        while (temp.next != null) {
            stack.push(temp.val);
            temp = temp.next;
        }
        while (head.next != null) {
            Integer nowValue = stack.pop();
            if (!Objects.equals(nowValue, head.val)) {
                return false;
            }
        }
        return true;
    }

    /***
     * 单链表是否回文
     * 使用栈实现，空间复杂度O（n/2）
     *
     * 使用快慢指针，快指针一次走两步，慢指针一次走1步
     * 当快指针的下一个节点指向null时候，慢指针在中点（奇数个节点）
     * 或者中点的前半个节点（假设偶数是中点是中间两个节点的中间，那么慢指针在中间两个节点的前一个）
     *
     * 把后半部分加入到栈中，在和前半部分进行比较
     * 如果全部一样那么回文，反之不回文
     *
     * 如果是 1->2->3->2->1,mid为3 栈依次加入2 1
     * 从head开始 如果遍历一个就pop一个
     *
     * 如果是1->2->3->3->2->1 mid为第一个3 栈依次加入3，2，1
     * 当head！=mid.next的时候，依次遍历
     */
    public static boolean isTheSingleLinkedListPalindrome2(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode fast = head;
        ListNode slow = head;
        //是否是奇数个节点
        boolean isOdd = false;
        while (fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
            fast = fast.next;
            if (fast != null && fast.next == null) {
                isOdd = true;
            }
        }
        ListNode mid = slow;
        while (slow.next != null) {
            stack.push(slow.next.val);
            slow = slow.next;
        }
        if (isOdd) {
            mid = mid.next;
        }
        while (head != mid) {
            Integer nowValue = stack.pop();
            if (!Objects.equals(nowValue, head.val)) {
                return false;
            }
            head = head.next;
        }
        return true;
    }


    /***
     * 单链表是否回文
     * 空间复杂度O（1）
     *
     * 使用快慢指针，快指针一次走两步，慢指针一次走1步
     * 当快指针的下一个节点指向null时候，慢指针在中点（奇数个节点）
     * 或者中点的前半个节点（假设偶数是中点是中间两个节点的中间，那么慢指针在中间两个节点的前一个）
     *
     * 把后半部分反转，在进行比较
     * 如果全部一样那么回文，反之不回文
     *
     * 1->2->3->2->1反转为 1->2->3->1->2
     * 1->2->3->4->2->1反转为 1->2->3->1->2->4,
     */
    public static boolean isTheSingleLinkedListPalindrome3(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
            fast = fast.next;
        }
        ListNode mid = slow;
        ListNode midNext = reverse(mid);
        ListNode rStart = midNext;
        ListNode tempHead = head;
        while (rStart != null) {
            if (tempHead.val != rStart.val) {
                return false;
            }
            tempHead = tempHead.next;
            rStart = rStart.next;
        }
        return true;
    }


    private static ListNode reverse(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }
        ListNode pre = null;
        ListNode cur = node;
        ListNode temp;
        while (cur != null) {
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    public static void main(String[] args) {
        ListNode listNode = ListNodeUtils.listGenerate(1, 2, 3, 2, 1);
        System.out.println(isTheSingleLinkedListPalindrome3(listNode));
//        ListNodeUtils.printList(reverse);
    }
}
